class Solution {
public:

    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        if(n==0) return true;
        vector<int> color(n, -1); //-1未访问 0 1两种颜色
        queue<int> q;

        q.push(0); color[0]=0;

        while(q.size())
        {
            int u=q.front(); q.pop();
            for(int v:graph[u]) 
            {
                if(color[v]==-1) {color[v]=!color[u]; q.push(v);}//如果没访问过
                else if(color[v]==color[u]) return false; //如果颜色相同
                //颜色不同则符合规则
                
            }
            if(q.empty()) //寻找起点
            {
                int st=0;
                while(st<n&&color[st]!=-1) st++;
                if(st==n) return true;
                q.push(st);  color[st]=0;
            }

        }
        return true;
    
    }
};